1. Field of the Invention
This invention relates to semiconductor memory and, more particularly, to a ternary Content Addressable Memory (CAM) cell that uses a shared bit and compare line, and employs no more than sixteen transistors when implemented as an SRAM based memory cell.
2. Description of the Related Art
The following descriptions and examples are not admitted to be prior art by virtue of their inclusion within this section.
CAM is a memory device designed to accelerate any application that requires extremely fast searches of a database, list, pattern, image, or voice recognition stored within a computer or a communication network. Contrary to conventional memory devices, CAMs do not store data in any structured fashion. The locations at which data is stored within a CAM can be random, where the data can be written directly into the first empty location within the CAM. Once data is stored in CAM, it can be found by comparing every bit in the CAM memory with data placed in a comparand register. If a match exists for every bit stored in a particular word line location within the CAM corresponding to every bit in the comparand register, a match line is asserted. Accordingly, a CAM operates opposite that of a conventional memory device by receiving data and returning an address.
One advantage of a CAM is that extremely quick searches can be undertaken, whereby the entire array of CAM cells is searched in a single clock cycle. If a match is found, the address is returned. That address is then used to retrieve data associated with the search string. The address is typically used to retrieve associated data stored in a discrete memory specified by the result of the CAM search.
CAM devices are particularly well suited for handling packet protocols, such as TCP/IP protocols employed in packet processors that are used to route information across an intranet or internet. Attributable to an intranet or internet is a packet-forwarding engine, oftentimes referred to as a switch or router. The switch or router receives the incoming packet and then parses the packet header to assemble the information related to the enclosed data, or payload. Additionally, the forwarding engine must extract relevant fields of bits to determine where and how to send the accompanying payload. The process of extracting source address information and forwarding the payload to a destination address may require multiple lookups.
A packet may contain both a destination network field and a destination host field. Beginning with the network destination field, a lookup will be needed to determine if the forwarding engine resides on a particular destination network. Thereafter, the forwarding engine must determine if, within the destination network, it resides upon a destination host. Internet protocol version 4 (IPv4) specification has established certain classes of segmentation. For example, class C IPv4 addresses have an 8-bit network ID field and a 24-bit host ID field. As the use of the internet has increased, the number of IPv4 addresses has also increased. Segmenting the host and destination fields can oftentimes be inefficient if, for example, a user is barely within an upper class usage, resulting in his/ her inefficient use of the IP addresses allocated to that user. Accordingly, a classless IP addressing scheme, referred to as Classless Inter-Domain Routing (CIDR), has arisen. According to CIDR, a floating boundary exists between the destination network field and the destination host field. The network field indicates the xe2x80x9cprefix lengthxe2x80x9d of the CIDR address.
With the advent of CIDR, a need existed for producing a new generation of CAMs. The ternary CAM, or TCAM, is designed to take advantage of the CIDR addressing scheme. In the routing table of a TCAM, entries are ordered such that the CIDR address with the longest prefix (the greatest number of bits in the network field) may be located in the lowest numerical address of the TCAM. The TCAM, therefore, has a main memory cell array and a mask memory cell array, where the main memory cell is used to store, for example, the network destination address. The mask memory cell can store a masking bit. The array of masking cells are, therefore, used to mask certain bits from the lookup operation. For example, the masking bits could be those of the host field, such that faster lookup can occur on only the network field first, followed by unmasked host field lookup second.
While TCAMs prove helpful in speeding up the routing process, especially in CIDR addressing, TCAM cells can be quite large -resulting in large die sizes. While it is desirable to utilize the features of a TCAM, it is also desirable to minimize the size of a TCAM cell and, thus, the size of an array of TCAM cells within a TCAM device. The desired TCAM device should, therefore, be relatively small and not suffer the burden of using extra bit lines and compare lines of conventional cells. The desired TCAM cell of minimal size would not only be more cost effective to make, but also allow for a larger array of cells to accommodate the increasing size of routing tables contained therein. In addition, as the cell size increases, so does the die size, which may lead to issues with viable manufacturability (due to increased manufacturing defects and consequent low yields) especially at higher densities.
The problems outlined above are in large part solved by an improved ternary content addressable memory (TCAM) device. A TCAM, in general, contains an array of main memory cells, mask memory cells, and compare circuits. In one feature of the present invention, further saving of area is achieved by encoding of the xe2x80x9cvaluexe2x80x9d and xe2x80x9cmaskxe2x80x9d of the main memory cell and mask memory cell (in circuitry external to the memory array) and the resultant bit-encoded values are stored in what is hereinafter known as an xe2x80x9cXxe2x80x9d memory cell and a xe2x80x9cYxe2x80x9d memory cell. A TCAM cell within the array employs a compare circuit interposed between the X memory cell and the Y memory cell.
For each TCAM cell, a single bit line/compare line conductor is used. The bit line/compare line conductor, or common conductor, is connected to the X memory cell, the Y memory cell, and the compare circuit. The common conductor can receive a voltage value to be stored in the X memory cell or the Y memory cell during a write operation, or to be read from the X memory cell or the Y memory cell, and can also receive a voltage value to be compared with the previously stored voltage value within the X and Y memory cells. The common conductor, therefore, can receive data to be written to or read from the X memory cell or the Y memory cell, or data to be compared with previously stored data in the X and Y memory cells.
A write operation can be encoded based on the value of a bit forwarded with a packet. The write operation indicates that a user is intending to change, for example, the routing tables within the TCAM cell. By writing a new voltage value at one or more X and Y memory cells, the user can change the packet-forwarding engine attributable to the TCAM. Thereafter, quick lookup can occur by performing a compare operation of subsequently sent packets with the network identification field or host identification field stored within the memory cell array. If the comparison indicates a match with all corresponding bits within a CAM word, then a match line will yield a logic value that is then presented to a priority encoder. In the case of a multiple match, the priority encoder will select the match line entry that has the lowest numerical address within the memory array (i.e., the address having the longest matching prefix).
The common conductor is therefore used not only during the write and read operations, but also during the compare operation based on the encoding of bits indicative of the operation being employed. Either the bit value being written to the memory cell or being read from the memory cell, or the bit value being compared with previously stored values are multiplexed onto a differential pair of common conductors (one conductor being the bit line/compare line, and the other conductor being the complimentary bit line/complimentary compare line).
Multiplexed bit line/compare line will avoid having to use additional lines, where one line is dedicated to receiving the compare signal and another line is dedicated to receiving the bit line signal. Avoiding an additional two conductive lines (i.e., two metal lines) of a conventional, differential TCAM cell not only reduces the size of the cell, but also the complexity by which it is interconnected with other TCAM cells within the overall array. It is contemplated that the transistors can be formed of numerous Field Effect Transistor (FET) technologies, including Metal Oxide Semiconductor (MOS) or bipolar.
According to one embodiment, the TCAM cell uses six transistors in the X memory cell portion, six transistors in the Y memory cell portion, and four transistors in the compare circuit portion. The 16 transistors are repeated for each TCAM cell across the array of TCAM cells. A mere savings of one transistor per TCAM cell could equate to several thousand transistors if there are, for example, 256 CAM words, each bearing a 48-bit length (i.e., 256xc3x9748).
According to another embodiment, the storage cell is coupled to store a first voltage value forwarded across the common conductor. The first voltage value can be a logic 1 or logic 0 voltage value that is placed within, for example, a X memory cell and a logic 1 or logic 0 value that is placed within, for example, a Y memory cell. The compare circuit suffices to compare the logic 1 or logic 0 voltage value placed within the X memory cell and the logic 1 or logic 0 voltage value placed within the Y memory cell (collectively called first voltage value) with a logic 1 or logic 0 voltage value (second voltage value) forwarded to the memory. The conductor, therefore, receives written data or compares data at dissimilar times, each of which are multiplexed onto the conductor.
The X memory cell and the Y memory cell preferably include latches which can store a voltage value for an indefinite period of time, provided power is retained on the memory cell. The compare circuit is configured to receive a match line and a match line enable. The match line indicates the result of a compare operation, and the match line enable can be selectively coupled to power or ground, for example. The match line can be pulled to power through a pull-up transistor. If, during the compare operation, data stored in the X and Y memory cells matches the incoming data, then the outcome is a match and the match line remains pre-charged to power. The match line enable is coupled to ground during a compare operation in order to pull down the match line if the outcome is not a match. However, during a read or write operation (when compare is not being performed), the match line enable conductor is placed at a power voltage level equivalent to the power level at which the match line is pre-charged. Placing a power supply voltage upon the match line enable to equal the pre-charged match line will effectively cause the compare circuit to be deactivated during the read or write operation, and no current path can exist through the four transistors of the compare circuit. As such, the compare circuit consumes no power during a read/write operation, and can only consume power during a compare operationxe2x80x94when a match does not exist, i.e., when the match line is pulled down from its pre-charged state to the voltage level (ground) on the match line enable.